#include <bits/stdc++.h>

using namespace std;

// 实现LFU结构
// 测试链接 : https://leetcode.cn/problems/lfu-cache/

class Node
{
public:
    int key, val, freq;
    Node* prev;
    Node* next;

    Node(int k = 0, int v = 0, int f = 1)
        : key(k), val(v), freq(f)
        , prev(nullptr), next(nullptr)
    {}
};

class LFUCache 
{
private:
    int minFreq;
    int cap;
    // 通过 freq 找到哨兵位头结点，也就进行缓存淘汰了
    unordered_map<int, Node*> freqToDummy; 
    // 通过 key 值找到其在双向链表的位置
    unordered_map<int, Node*> keyToNode;

    // 将 node 节点从原来的双向链表移出，但不一定要删除
    // 这个节点，因为可以 put 函数可以复用这个节点
    void remove(Node* node)
    {
        // prev node next
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // 申请一个新的哨兵位头结点，也
    // 就是多了一个双向链表
    Node* newDummy()
    {
        Node* dummy = new Node();
        dummy->next = dummy;
        dummy->prev = dummy;
        return dummy;
    }

    // 将 node 节点头插到对应的双向链表中
    void frontInsert(int freq, Node* node)
    {
        // 没有 freq 这个频次的双向链表，则需要新建出一个双向链表
        if(!freqToDummy.count(freq))
        {
            freqToDummy[freq] = newDummy();
        }
        // 将 node 头插到双向链表中，双向链表头部的元素是
        // 该频次出现最晚的一个元素
        // dummy node next
        Node* dummy = freqToDummy[freq];
        Node* next = dummy->next;
        dummy->next = node;
        node->prev = dummy;
        node->next = next;
        next->prev = node;
    }

    // 查找 key 值所在的位置，如果 key 值不存在，则返回 nullptr
    Node* getNode(int key)
    {
        auto it = keyToNode.find(key);
        // key 值不存在
        if(it == keyToNode.end()) return nullptr;
        
        Node* node = it->second;
        remove(node); // 将 node 节点从原来的双向链表中移出
        int freq = node->freq; // 这个 key 值原来出现的频次
        Node* dummy = freqToDummy[freq]; // 该 key 值原来所在的双向链表
        if(dummy->next == dummy)
        {
            freqToDummy.erase(freq); // freq 频次的双向链表没有元素了
            delete dummy; // 释放内存
            if(freq == minFreq) ++minFreq; // key 的出现频次即将成为最小的出现频次
        }
        // 将 node 节点头插到 node->freq + 1 这个频次的双向链表中
        frontInsert(++node->freq, node); 
        return node;
    }

public:
    LFUCache(int capacity) 
    {
        cap = capacity;
        minFreq = 0;
    }
    
    int get(int key) 
    {
        Node* node = getNode(key);
        return node ? node->val : -1;
    }
    
    void put(int key, int value) 
    {   
        // getNode 会更新 key 的出现频次，并将其头插到对应的双向链表中
        Node* node = getNode(key); 
        // key 值已经存在
        if(node)
        {
            node->val = value; // 更新其 value 值
            return;
        }
        // key 值不存在
        if(keyToNode.size() == cap) // 缓存满了，要开始淘汰使用最少的缓存了
        {
            Node* dummy = freqToDummy[minFreq];
            // 尾节点是相同频次中最久未使用的，需要将其从缓存中删除
            Node* backNode = dummy->prev;
            keyToNode.erase(backNode->key);
            remove(backNode); // 将其移出双向链表
            delete backNode; // 释放内存
            if(dummy->next == dummy) // 链表为空
            {
                delete dummy; // 释放内存
                freqToDummy.erase(minFreq);
            }
        }
        node = keyToNode[key] = new Node(key, value);
        frontInsert(1, node); // frontInsert 接口会申请新的链表
        minFreq = 1;
    }
};